package code2;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 8:58
 *
 * 二分查找变种2：
 * 如果数组中存在元素target，则返回最大索引
 * 如果数组中不存在元素，返回 Upper【比目标值小的最小值的索引】
 *
 */
public class BinarySearchUpperCeil {

    // >target 返回最小值索引
    // ==target 返回最大索引
    public static <E extends Comparable<E>> int upper_ceil(E[] data,E target){
        int  u = upper(data,target);
        if( u- 1 >=0 && data[u-1].compareTo(target)==0){
            return u-1;
        }else{
            return u;
        }
    }



    //返回target的最小值索引
    public static <E extends Comparable<E>> int upper(E[] data,E target){
        int left = 0;
        int right = data.length;

        while (left < right){
            int mid = left + (right - left)/2;

            if(data[mid].compareTo(target) <= 0){
                left = mid + 1;
            }else  if(data[mid].compareTo(target) > 0){
                right = mid;
            }
        }

        //当left==right就是循环停止的条件
        return left; //返回right也是一样的


    }

    public static void main(String[] args) {
        Integer[] arr = {1,1,3,3,5,5};
        for (int i = 0; i <= 6 ; i++) {
            ;
            int search = BinarySearchUpperCeil.upper_ceil(arr, i);
            System.out.println( "求target="+i +"的ceil的索引为:"+search + " ");
        }
        System.out.println();
    }
    /*
求target=0的ceil的索引为:0    --target为0不存在，转换为求upper 所以索引是是0
求target=1的ceil的索引为:1    --target为1存在，所以就最大索引，所以索引为1(第二个1的下标)
求target=2的ceil的索引为:2
求target=3的ceil的索引为:3
求target=4的ceil的索引为:4
求target=5的ceil的索引为:5
求target=6的ceil的索引为:6
     */
}
